import java.util.HashMap;
import java.util.Map;

public class Solution52 {

    int ans=0;

    public int totalNQueens(int n) {
        boolean[] a= new boolean[n];
        Map<Integer,Boolean> map1=new HashMap<>();
        Map<Integer,Boolean> map2=new HashMap<>();
        dfs(0,n,a,map1,map2);
        return ans;
    }

    private void dfs(int k, int n, boolean[] a, Map<Integer, Boolean> map1, Map<Integer, Boolean> map2) {
        if (k==n){
            ans++;
            return;
        }
        for (int i=0;i<n;i++){
            if (!a[i] && !map1.getOrDefault(k+i,false) && !map2.getOrDefault(k-i,false)){
                a[i]=true;
                map1.put(k+i,true);
                map2.put(k-i,true);
                dfs(k+1,n,a,map1,map2);
                a[i]=false;
                map1.remove(k+i);
                map2.remove(k-i);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution52().totalNQueens(4));
    }
}
